package com.jack.leetcode.每日一题;

import java.sql.Timestamp;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;

/***
 * @author zhangjie
 * @date 2020/4/5 14:48
 */
public class LFUCache {

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.get(1);       // 返回 1
        cache.put(3, 3);    // 去除 key 2
        cache.get(2);       // 返回 -1 (未找到key 2)
        cache.get(3);       // 返回 3
        cache.put(4, 4);    // 去除 key 1
        cache.get(1);       // 返回 -1 (未找到 key 1)
        cache.get(3);       // 返回 3
        cache.get(4);       // 返回 4
    }

    Map<Integer,Node> cache;
    Map<Integer, LinkedHashSet<Node>> freqMap;
    int size;
    int capacity;
    int min;

    public LFUCache(int capacity) {
        this.cache = new HashMap<>(capacity);
        this.freqMap = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if(node == null){
            return -1;
        }
        freqInc(node);
        return node.value;
    }

    public void put(int key, int value) {
        if(capacity == 0){
            return;
        }
        Node node = cache.get(key);
        if(node != null){
            node.value = value;
            freqInc(node);
        }else{
            if (capacity == size) {
                Node removeNode = removeNode();
                cache.remove(removeNode.key);
                size--;
            }
            Node newNode = new Node(key,value);
            cache.put(key,newNode);
            addNode(newNode);
            size++;
        }

    }

    void freqInc(Node node){
        int freq = node.freq;
        LinkedHashSet<Node> set = freqMap.get(freq);
        set.remove(node);
        if(freq == min && set.size() == 0){
            min = freq+1;
        }
        node.freq++;
        LinkedHashSet<Node> newSet = freqMap.get(freq+1);
        if(newSet == null){
            newSet = new LinkedHashSet<>();
            freqMap.put(freq+1,newSet);
        }
        newSet.add(node);
    }

    void addNode(Node node){
        LinkedHashSet<Node> set = freqMap.get(1);
        if(set == null){
            set = new LinkedHashSet<>();
            freqMap.put(1,set);
        }
        set.add(node);
        min = 1;
    }

    Node removeNode(){
        LinkedHashSet<Node> set = freqMap.get(min);
        Node removeNode = set.iterator().next();
        set.remove(removeNode);
        return removeNode;
    }

    class Node{
        int key;
        int value;
        int freq = 1;
        public Node(){}

        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
}
